WORST_CASE(?,O(n^1)) * Step 1: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: div(x,y) -> h(x,y,y) egypt(div'(0(),y)) -> nil() egypt(div'(s(x),y)) -> app(div(y,s(x)),egypt(i(div'(s(x),y),div'(s(0()),div(y,s(x)))))) h(s(0()),y,z) -> s(0()) h(s(s(x)),s(0()),z) -> s(h(s(x),z,z)) h(s(s(x)),s(s(y)),z) -> h(s(x),s(y),z) i(div'(x,y),div'(u,v)) -> div'(minus(mult(x,v),mult(y,u)),mult(y,v)) - Signature: {div/2,egypt/1,h/3,i/2} / {0/0,app/2,div'/2,minus/2,mult/2,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {div,egypt,h,i} and constructors {0,app,div',minus,mult ,nil,s} + Applied Processor: Ara {araHeuristics = NoHeuristics, minDegree = 1, maxDegree = 2, araTimeout = 5, araRuleShifting = Nothing} + Details: Signatures used: ---------------- 0 :: [] -(0)-> "A"(12) 0 :: [] -(0)-> "A"(4) 0 :: [] -(0)-> "A"(0) 0 :: [] -(0)-> "A"(15) app :: ["A"(0) x "A"(0)] -(0)-> "A"(12) div :: ["A"(4) x "A"(2)] -(1)-> "A"(0) div' :: ["A"(12) x "A"(12)] -(0)-> "A"(12) div' :: ["A"(0) x "A"(0)] -(0)-> "A"(0) div' :: ["A"(15) x "A"(15)] -(0)-> "A"(15) egypt :: ["A"(12)] -(8)-> "A"(8) h :: ["A"(4) x "A"(0) x "A"(0)] -(0)-> "A"(0) i :: ["A"(0) x "A"(0)] -(2)-> "A"(15) minus :: ["A"(0) x "A"(0)] -(0)-> "A"(15) mult :: ["A"(0) x "A"(0)] -(0)-> "A"(12) mult :: ["A"(0) x "A"(0)] -(0)-> "A"(4) mult :: ["A"(0) x "A"(0)] -(0)-> "A"(15) nil :: [] -(0)-> "A"(15) s :: ["A"(12)] -(12)-> "A"(12) s :: ["A"(4)] -(4)-> "A"(4) s :: ["A"(0)] -(0)-> "A"(0) s :: ["A"(2)] -(2)-> "A"(2) Cost-free Signatures used: -------------------------- Base Constructor Signatures used: --------------------------------- "0_A" :: [] -(0)-> "A"(1) "app_A" :: ["A"(0) x "A"(0)] -(0)-> "A"(1) "div'_A" :: ["A"(1) x "A"(1)] -(0)-> "A"(1) "minus_A" :: ["A"(0) x "A"(0)] -(0)-> "A"(1) "mult_A" :: ["A"(0) x "A"(0)] -(0)-> "A"(1) "nil_A" :: [] -(0)-> "A"(1) "s_A" :: ["A"(1)] -(1)-> "A"(1) WORST_CASE(?,O(n^1))